/* 动态规划 最大正方形 */

#include<iostream>
#include<cmath>
using namespace std;

struct TMaxSquare
{
	int row;
	int col;
	int area;
};

int main(void)
{
	constexpr int ROW = 4;
	constexpr int COL = 5;

	char squares[ROW][COL] = {
		{48, 48, 49, 48, 48},
		{49, 48, 48, 48, 48},
		{48, 48, 48, 49, 48},
		{48, 48, 48, 49, 48}
	};

	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			cout<< (char)squares[i][j] << " ";
		}
		cout<< "\n";
	}


	int dq[ROW][COL];
	for (int j = 0; j < COL; j++)
	{
		dq[0][j] = ('0' == squares[0][j]) ? 1 : 0;
	}
	for (int i = 1; i < ROW; i++)
	{
		dq[i][0] = ('0' == squares[i][0]) ? 1 : 0;
	}

	TMaxSquare t = {0, 0, 1};
	for (int i = 1; i < ROW; i++)
	{
		for (int j = 1; j < COL; j++)
		{
			if (squares[i][j] == '1')
			{
				dq[i][j] = 0;
			}
			else
			{
				dq[i][j] = min(dq[i - 1][j - 1], min(dq[i][j - 1], dq[i - 1][j])) + 1;

				if (dq[i][j] > t.area)
				{
					t.area = dq[i][j];
					t.row = i;
					t.col = j;
				}
			}
		}
	}
	
	int length = sqrt(t.area);
	cout<< "area of the max square is: " << t.area * t.area <<endl;
	for (int i = 0; i < t.area; i++)
	{
		for (int j = 0; j < t.area; j++)
		{
			squares[t.area - i][t.area - j] = 'x';
		}
	}
	
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			cout<< (char)squares[i][j] << " ";
		}
		cout<< "\n";
	}

	return 0;
}

